Пар производа у ранцу
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,25 s | 64 Mb | стандардни излаз | стандардни улаз |
Ненад је отпутовао у Париз и жели да купи поклоне својим родитељима. Пошто путује нискотарифном авио-компанијом, ограничена је маса коју може да понесе у свом ранцу. Оцу ће купити поклон у једној, а мајци у другој продавници. Напиши програм који на основу познатих маса и цена поклона у обе продавнице помаже Ненаду да родитељима купи што вредније поклоне (гледајући њихову укупну цену).
Улаз
Са стандардног улаза се уносе подаци у производима у две продавнице. За сваку продавницу се уноси број производа \(n\) \((1 \leq n \leq 10^5)\), и затим у наредних \(n\) линија по два цела броја, сваки између \(1\) и \(10^9\), који представљају масу и затим цену производа. Након тога се уноси и укупна маса поклона коју је могуће понети у ранцу (цео број између 1 и \(2\cdot 10^9\)).
Излаз
На стандардни излаз исписати највећи могући збир цена првог и другог поклона које је могуће понети у ранцу.
Пример
Улаз
3 2 4 3 6 4 5 3 2 3 3 2 4 5 6
Излаз
9
Овај задатак има и другачија решења у делу збирке који следи.
Морате бити улоговани како бисте послали задатак на евалуацију.